COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002				Rules for "Bugs and Loops"
C00007 00003				Use of the "BLOOP" program
C00015 00004				What is a Turing machine?
C00021 ENDMK
C⊗;
			Rules for "Bugs and Loops"


	Bugs and Loops is a game  played on a Turing machine.  If  you
don't already know what one of these marvelous playthings is, read the
description on the last page of this documentation.

	It would  be more  accurate to  say the  game is  played on  a
"stripped-down" Turing machine  (if such  a thing  is possible).   The
tape is finite; its length is  specified at the beginning of the  game
(longer tapes make for  a more complex game).   Each cell of the  tape
may contain any one of  four symbols:  B, G, R,  and Y.  (If you  must
know: blue, green, red, and yellow.)  The machine may be in any one of
four states: B,  G, R,  and Y.   (Gee, why  do those  letters look  so
familiar?)  Instructions to the machine are written in the form:

    <current-state><current-symbol><new-state><new-symbol><motion>

where the legal motions are ← (one cell left), → (one cell right), and
↓ (stay put).  (For the benefit  of poor souls with limited  character
sets, the characters <, >, and = are also accepted by the program.)

	Players take turns adding single instructions to the machine's
repertoire.  After each instruction is  added, the machine is  stepped
until it reaches a configuration for  which it has no rule.  For  each
step it takes,  the player  who added  the latest  instruction gets  a
point.  HOWEVER, if  the machine  runs off the  end of  the tape,  the
situation is called  a "bug".  If  it enters an  infinite loop, it  is
called a  "loop".  If  either  of these  situations occurs,  then  the
following special actions are taken:

[1]  The player who added the latest rule scores nothing.  (His  score
     is reset to whatever it was before his latest turn.)

[2]  The tape  is restored  to  the condition  it  was in  before  the
     current turn was taken.

[3]  The rule which was added on this turn STAYS in the repertoire.

[4]  The next player gets to move the tape head to any position on the
     tape, and put the machine in any of the four states.  It is  then
     that player's turn.

It is obvious that bugs and loops  are things to be avoided, yet  they
have a way of turning up anyway.  That's the name of the game.

	Players are not  allowed to "overwrite"  rules already in  the
repertoire.  That  is,  if  there  is  already  a  rule  for  a  given
state-symbol combination, it is illegal to enter another rule for  the
same combination.   Since  there  are only  16  possible  state-symbol
combinations, it is clear that something must be done to avoid  having
the repertoire fill up.   In fact, as the  number of rules  approaches
16, it  rapidly becomes  impossible  to avoid  having  a bug  or  loop
(unless the new rule  simply changes to  a halt-combination in  place,
and even  this  can't be  done  for the  16th  rule).  To  avoid  this
problem, the repertoire  is purged automatically  after every  twelfth
turn.

	The game is  won when one  player, at  the end of  his or  her
turn, has a score of  21 or more.  (In  case you hadn't guessed,  that
player is the winner.)
			Use of the "BLOOP" program


	To play Bugs and Loops,  RUN SYS:BLOOP.  The program asks  for
various helpful information, such as number of players and size of the
tape.  If there  are two  or more human  players (maximum  of 5),  the
program asks for their names, and also asks if it should play too.  If
there is only one  human player, the program  refers to the player  as
"you", and assumes that it should be your opponent.  Be warned, it  is
a  nasty   opponent!   Most   of  the   information  is   entered   as
single-character inputs (no  carriage returns),  the exceptions  being
the length of the tape (which may be as large as 10) and the  players'
names.  During  the  game,  rules are  input  with  trailing  carriage
returns,   other   input   (interrupt   options   (see   below)    and
tape-position/machine-state after a bug or loop) as single characters.
Note: When positioning the tape head after a bug or loop, if you  want
the last cell of a 10-cell tape, you have to type ":" (the ASCII  code
following "9").  This kluge may be fixed some day.

	Various interesting  options  are provided  via  an  interrupt
feature.  To invoke the interrupt feature from a display, type <esc>I.
From a TTY  or similar  deprived terminal,  hit ↑C  and REENTER.   The
interrupt processor will be invoked just after the next rule has  been
typed or  just before  the display  is next  changed, whichever  comes
first.  The processor will list  the available options and await  your
selection.  After each selection, it will perform the required actions
and ask  for another  selection.  This  keeps up  until you  type  any
illegal character, whereupon the program proceeds with whatever it was
doing.  You  need not  request  any legal  options  at all;  thus  the
interrupt feature may be used to freeze the game momentarily while you
study the  configuration,  twiddle your  thumbs,  or fetch  a  cup  of
coffee.

	The options currently include:

X...to produce an XGP listing of the current display
T...to have  the  program  print all  future  machine  configurations,
    scores, etc., on the page printer, in case someone is playing  via
    a non-display terminal
D...to turn  off the  page printer  stuff and  use only  the  DataDisc
    display hacks
P...to print the current situation on  the page printer (this may  not
    correspond to the current  display, since the  if the display  was
    about to be updated then it is the new situation which is shown)
B...to back up one turn (see below)
F...to produce a file containing a record of the game for future study
W...to write a program-readable file (save a game to be finished or
    replayed later)
R...to restore a game from a file written using the W option
S...to set an arbitrary configuration via the keyboard (if you have  a
    favorite starting position)
?...to list the options again (in case they've drifted off the screen)

	Notes:

[1] At the  end of  the  game, the  interrupt processor  is  activated
    automatically to give you  a chance to xspool  a final listing  or
    list the game or back up or whatever.

[2] Although you are  free to  type <esc>I as  soon as  you start  the
    program, the  interrupt  will  not be  processed  until  you  have
    answered all the opening questions, whereupon the display is about
    to be updated for the first time.

[3] If you are planning to use  the R option immediately, you  needn't
    worry about your  answers to  the opening questions,  since the  R
    option will override everything with the info stored in the file.

[4] Backing up and restoring (options B  and R) are permitted only  at
    the beginning of a turn or at the  end of a game.  If you ask  for
    one of  these options  at another  time, you  will be  told it  is
    illegal and an  interrupt will be  generated automatically at  the
    next point where the operation is legal.

[5] The R option leaves  you at the beginning  of the game, as  though
    you had backed up all  the way.  After using  the R or B  options,
    you may type "&" in place of a rule whenever one is requested, and
    the rule will be used which was played before at this point in the
    game.  However, as soon  as a legal move  is explicitly typed  (as
    opposed to  using the  "&"), it  becomes illegal  to use  the  "&"
    feature, since the forward progress of the game has been altered.

[6] The "&" feature currently does not provide a way to  automatically
    replay the prior  choice of  position/state after a  bug or  loop.
    This bug may get fixed some day.
			What is a Turing machine?


	A Turing machine  consists of a  recording device (usually  an
infinitely long tape) and  a read/write head  which may be  positioned
anywhere on the tape.  Each  cell of the tape may  be in any one of  a
number of `states', and  the Turing machine itself  is always in  some
`state'.  (The possible states of the machine and the possible  states
of cells on the tape need not be the same, although this happens to be
the case with "Bugs and  Loops".)  Turing machines are significant  in
the theory of  computation, since  they are known  to have  "universal
computability"; that is, anything which can be computed at all can  be
computed using a Turing machine.

	The  operation  of  the  machine  is  governed  by  a  set  of
`transition rules', each of which specifies:

Given	(1) the machine is in a certain state, and
	(2) the tape cell being scanned is in a certain state,
then	(1) put the machine in some (possibly different) state,
	(2) write a (possibly different) state in the tape cell, and
	(3) move the read/write head left one cell, right one cell, or
	    not at all

Let's make this clearer  with an example.  At  the same time, we  will
introduce the notation used by the bugs and loops program.

	Imagine a Turing machine with a 10-cell tape, where each  cell
(and the machine) may be in either of 2 states, empty [o] or full [⊗].
A typical configuration for this machine might be:

				   ⊗
				   ↓
			 ⊗ o o ⊗ ⊗ o o ⊗ ⊗ o

The upper line shows the machine in the full state, reading the  sixth
cell on the tape.  The lower line  shows (of all things) the tape.   A
transition rule for  the above configuration  might be:  ⊗o⊗⊗←   which
specifies, in order, "If the machine  is full and is reading an  empty
cell, then leave the machine in  the full state, change the tape  cell
to the full state,  and move to  the left."  We  will be denoting  the
other  directions  of  movement  by  →  and  ↓  for  right  and  stay,
respectively.  After the rule ⊗o⊗⊗←  was applied to the  configuration
given above, the Turing machine would look like this:

				 ⊗
				 ↓
			 ⊗ o o ⊗ ⊗ ⊗ o ⊗ ⊗ o

	Let's look at a more  complicated example.  Suppose we have  a
Turing machine with an  infinite tape.  Each cell  of the tape may  be
any one of 11 states--0 through 9, and x (empty).  The machine may  be
in any of 3 states,  which we will represent by  /, \ and -.   Suppose
that, somewhere on  the tape, we  have a number,  surrounded by  empty
cells, and that the machine is in  state /, reading the last digit  of
the number.

				      /
				      ↓
		  ..... x x x 1 3 6 9 9 x x x .....

The following  set  of transition  rules  would increment  the  number
represented on the tape.

		/0\1→   /1\2→   /2\3→   /3\4→   /4\5→
		/5\6→   /6\7→   /7\8→   /8\9→   /9/0←
			/x\1→   \0\0→   \x-x←

The machine would apply the  appropriate rule at each stage,  yielding
the following steps.

				    /
				    ↓
		  ..... x x x 1 3 6 9 0 x x x .....

				  /
				  ↓
		  ..... x x x 1 3 6 0 0 x x x .....

				    \
				    ↓
		  ..... x x x 1 3 7 0 0 x x x .....

				      \
				      ↓
		  ..... x x x 1 3 7 0 0 x x x .....

					\
					↓
		  ..... x x x 1 3 7 0 0 x x x .....

				      -
				      ↓
		  ..... x x x 1 3 7 0 0 x x x .....

At this point,  lacking a transition  rule for the  combination `-0',  the
machine halts.  Should something external cause the machine to enter state
/, the number will be incremented again.